package Day09;

/**
 * ---------------------------------------------------------------------------------------------------------------------
 * 题目：
 * 给定四个整数sx,sy，tx和ty，如果通过一系列的转换可以从起点(sx, sy)到达终点(tx, ty)，则返回 true，否则返回false。
 * 从点(x, y)可以转换到(x, x+y) 或者(x+y, y)。
 * ---------------------------------------------------------------------------------------------------------------------
 * 示例 :
 * 输入: sx = 1, sy = 1, tx = 3, ty = 5
 * 输出: true
 * 解释:
 *      可以通过以下一系列转换从起点转换到终点：
 *      (1, 1) -> (1, 2)
 *      (1, 2) -> (3, 2)
 *      (3, 2) -> (3, 5)
 * ---------------------------------------------------------------------------------------------------------------------
 * 方法：反向计算
 * 如果 tx>sx 并且 ty>sy 并且 tx!=ty 就循环反向计算
 *      如果 tx=ty，不存在上一个状态，状态 (tx,ty) 即为起点状态，
 *      如果 tx>ty，则上一个状态是 (tx−ty,ty)，
 *      如果 tx<ty，则上一个状态是 (tx,ty−tx)。
 * 如果循环结束，则进行判断
 *      如果 tx=sx,ty=sy，则找到起点，
 *      如果只有 tx=sx，那么表示ty>sy，则看ty-sy是不是tx的倍数，如果是，则能倒回起点
 *         只有 ty=sy，情况同上
 *      都不想等那就没有找到起点。
 * ---------------------------------------------------------------------------------------------------------------------
 */

class Solution {
    public static void main(String[] args) {
        System.out.println(reachingPoints(1,1,3,5));
    }
    public static boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        if (tx == sx && ty == sy) {
            return true;
        } else if (tx == sx) {
            return ty > sy && (ty - sy) % tx == 0;
        } else if (ty == sy) {
            return tx > sx && (tx - sx) % ty == 0;
        } else {
            return false;
        }
    }
}